Preliminary Remarks on the

                          National Bureau of Standards


                               Proposed Standard


               Encryption Algorithm for Computer Data Protection





                                    May 1975







                                Whitfield Diffie
                         Information System Laboratory
                       Electrical Engineering Department

                              Stanford University









                                 Acknowledgement

	I am deeply indebted to Professor Martin Hellman for  his  encouragement
and  criticism in the preparation of these remarks.    He has made many valuable
suggestions influencing both the content and readability of the paper.







This work was supported under NSF Grant GK - 33250




	Most  of  the  commentary which follows will be critical of the proposed
encryption algorithm in one way or another. As the algorithm has been put  forth
for  public  scrutiny  and  comments, we feel that this is entirely appropriate.
Nothing that we say, however, should be interpreted as disparaging  the  efforts
of  either  IBM  or the Bureau. On the contrary, we feel that IBM by introducing
the Lucifer family of block cipher systems, has made an outstanding contribution
which  will  have  far  reaching  effects  on  both  theory  and  application in
cryptography.  NBS by undertaking the difficult task of formulating,  evaluating
and  promulgating standards in this field has likewise rendered it an invaluable
service.

	As we have had relatively little time to study the proposed cipher,  and
have had to do so without benefit of the still forthcoming NBS technical note on
the  subject,  these  remarks  are  admittedly  preliminary,  speaking  more  to
questions of use and implementation than to the quality of the algorithm itself,
many aspects of which remain obscure to us.

	We feel that NBS should be congratulated on the quality of the technical
presentation,  which  clearly  conveys the operation of the algorithm.  What has
been published so far leaves many questions  unanswered,  however.  The  precise
contributions of some of its elements are unclear, while the way in which others
are presented suggests an underlying structure which has yet to appear in print.
We  hope  that when the technical note is published it will answer many of these
questions.

	Some of the work described below  is  still  unfinished.  We  expect  to
prepare  a  more  thorough  critique  of the algorithm and its applications at a
later date.


	The  most characteristic and most difficult problem in the evaluation of
an  encryption  algorithm  is  the  question  of  security.   At  present,   the
development  of a theory adequate to guarantee the strength of a cryptosystem is
in its infancy, and current certification efforts rest on mounting a  determined
cryptanalytic  assault on the system under study. Repeated efforts of this sort,
either by parties wishing to participate in  the  standard  making  process,  or
later  by  prospective  users  would be redundant and wasteful.  In the years to
come, we can  expect  an   ever  increasing  application  of  digital  computing
facilities to the handling of monetary transactions and other vital data. Before
these data can be entrusted to a standardized system of protection, it  must  be
subjected to thorough public scrutiny to guarantee that any prospective user may
assure himself without undue hardship  that  its  security  is  above  reproach.
Perhaps  equally  important will be an effort to ensure that the most profitable
course of action for anyone who does breach the system, will be to bring this to
public notice rather than attempt to profit covertly from his knowledge.

	In  order  to  further these goals, we feel that the Bureau of Standards
should undertake to make available  substantially  more  information  about  the
algorithm,  and the reasons for which it was selected. A major component of this
exposition should be a survey of all the various systems submitted  in  response
to  the  two Federal Register solicitations, together with an explanation of the
rationale behind the final choice.

	We understand that IBM has  conducted  both  statistical  and  algebraic
studies  of  the  system. To date, the only products of these studies which have
come to our attention are the group theoretic papers of Grossman and Coppersmith
[5  and  6].  The  rest  of  this material should be brought to light and widely
disseminated both for direct evaluation and as  a  starting  point  for  further
work.



	The notice  "License  Under  Patents"  which  accompanies  the  proposed
encryption algorithm [8], opens:

	"In   the   normal  case,  the  Department  of  Commerce  establishes  a
performance standard which does not  require  the  use  of  any  patent  in  its
implementation.   In  the  present  case,  it  is not possible to meet an urgent
national need for security in computer  systems  with  a  performance  standard.
Rather,  it  will be necessary to establish a design standard which requires the
use of an algorithm."

	We feel that the possibility of  a  performance  standard  is  dismissed
here,  without  adequate  hearing.   Although  it seems certain that one or more
derivative design standards will  be  necessary,  we  feel  that  a  performance
standard,  against  which  proposed ciphers can be judged, is also required, and
should be developed at the earliest possible date.


	A  cryptographic  standard, of any form, must answer conflicting demands
of flexibility and compatibility; a conflict which is more difficult to  resolve
in  this  instance than elsewhere in the data processing field. On the one hand,
cryptography  may  profitably  be  adapted  to  various  applications  differing
substantially  in  the  degree  of  security required, the hardware and software
resources available and other cost and performance considerations. On the other,
cryptographic  communication  between any two parties requires that they hold at
least one specific cryptosystem in common. An adequate national standard  should
speak to both of these issues.

	The  use  of a single design standard offers an advantage more difficult
to obtain in other ways. Any two parties desiring to establish cryptographically
secure communications need only exchange keys via a suitable secure channel such
as registered mail. In particular, the owner of an encrypted file  stored  in  a
public  data  facility,  may  give  another  party  access to the data merely by
mailing him the key.

	The benefits would be substantial, and may be likened to those we  would
derive  from  adopting  a  uniform  format  for magnetic tapes or establishing a
universal programming language. The reasons for avoiding this course  of  action
may  also  be  similar.   Just  as  no  language  has  proven well suited to all
programming applications, it seems likely that no single cryptosystem will  meet
the  needs  of  all  potential  users  equally.   The  gains  to be derived from
compatibility, though substantial, may not justify the cost  of  a  cryptosystem
ill suited to day to day use.

	As  shown  below,  there  are  many  applications for which the proposed
algorithm is not well suited. The blocksize is too short for  efficient  storage
or  shipment  of  large  quantities  of data and too long for efficiency in some
interactive situations.

	If large quantities of data are to be protected cryptographically, using
a  block  cipher,  some form of chaining between blocks is required to guarantee
the integrety of the data with respect to addition, deletion,  or  rearrangement
of blocks [2, 3, and 4]. The security derived from the addition of authenticator
fields varies with the absolute rather than relative sizes of these fields. Thus
if  thirty  bits  of authenticator are included in each block, the chances of an
illegitimate block being found acceptable are one  in  a  billion  whereas  with
twenty  bits  they  are  only  one in a million, regardless of the blocksize. In
circumstances demanding a high degree of security,  authenticators  thirty  bits
long  or  longer  do  not  seem  excessive.   The  inclusion  of  a  thirty  bit
authenticator field in a 64 bit block gives an efficiency of only fifty percent,
which  might  substantially increase storage or transmission costs. A block size
of 256 bits, by comparison, would allow an efficiency of nearly ninety percent.


	At the other end of the scale is full duplex interaction between a  user
and  a  computer, where many user transmissions will be only one character long.
In this case, 32 bits might  suffice  for  the  whole  message  block  including
authentication information.


	The keysize is at best barely adequate. Even today, hardware capable  of
defeating  the system by exhaustive search would strain, but probably not exceed
the budget of a large intelligence organization. As the feasibility  of  such  a
project  depends  on  on  the  cost and speed of the crypto hardware, its future
seems bright. Widespread application  of  such  cryptographic  devices  in  data
processing  can be expected to make a substantial reduction in costs, while some
applications, such as encrypting data on high speed disks  [7],  will  encourage
the development of very fast hardware.

	Suppose,  for  example,  the  proposed  algorithm  were implemented on a
single chip, capable of doing the full operation in one microsecond and  costing
a  dollar.   The  cost  of  a simulator able to do a quarter of a million crypto
operations simultaneously would by substantially less than  a  million  dollars.
With  this degree of parallelism, the key space could be searched in two hundred
and fifty-six billion machine cycles. On average only half of the key space need
be  searched,  permitting  the cryptanalysis to be carried out in about one day,
provided the correct plaintext could be recognized when produced. Though  highly
dependent  on  the particular cryptographic application under attack, this would
certainly be possible in many  cases.   Since  this  technique  yields  the  key
directly,  rather  than just the contents of a single message block, all traffic
enciphered with this key becomes accessible.

	Although cryptanalysis by exhaustive search is far  from  cheap,  it  is
also  far  from  impossible,  and  even  a  small  improvement  in cryptanalytic
technique could dramatically improve the cost performance picture.   We  suggest
doubling the size of the key space to preclude searching.


	The availability of hardware  capable  of  executing  the  block  cipher
quickly  will  not  meet  the  needs  of  many existing facilities, which handle
volumes of sensitive date insufficient to justify the cost  of  interfacing  new
hardware.     These   users   will   require  a  reasonably  efficient  software
implementation.

	From the point of view of software implementation, the design  seems  to
favor  the  IBM  hardware configuration. Implementation on a machine in which 8,
16, 32 and 64 bit quantities are not the natural ones is extremely awkward. Such
machines  include  the GE 635 and 645, Digital PDP 8, 10 and 15, the SDS 940 and
others.

	A study of this problem for a similar encryption  algorithm  implemented
on  the  MIT  Multics  timesharing  system concludes that the most rapid machine
language version of the program would slow down IO by a factor of  four,  making
it suitable for only occasional use [1].

	It  is possible, however, that even on IBM systems speed is difficult to
achieve. Implementations for the IBM 360 described in [3] and [10] give  figures
of several milliseconds per 128 bit block, but these times are not compared with
those for unenciphered system IO.

	We  have  begun,  but  not  completed,   a   program   of   experimental
implementation  of  the cipher in software on the Digital PDP-10. When this work
is finished, we will be in a position to evaluate the overhead  which  would  be
imposed by encryption on such standard processes as editing and copying.


	Some  of  the  objections  raised earlier, regarding flexibility, may be
answered by adoption of application standards in which  the  present  encryption
method  becomes a building block. This would be likely to require use of the IBM
step coding technique, the patent (No.    3,798,360)  for  which  has  not  been
explicitly licensed for public use.


	In light of a diversity of applications at present, and  unknown  future
needs,  we  propose  that  a  more  flexible  standard should be adopted. Such a
standard might specify a parametrized family of block ciphers.    The  principal
parameter would be block length, but flexibility in such things as the number of
rounds and keysize might be provided for the convenience  of  those  wishing  to
implement  low  grade cryptosystems at lower computational expense. Under such a
standard, the recipient of enciphered data would need to  know  the  blocklength
and  number  of  rounds employed as well as the key. In individual applications,
the block size could be chosen for compatibility with data  format,  instruction
set  etc.  At the same time, this family of block ciphers should be founded on a
minimal set of primitive elements; for example a common set of  S-boxes.    This
would  allow  the  construction  of  a general purpose crypto program capable of
preforming the block cipher on blocks of any length. This  program  would  serve
the  needs  of  compatibility,  permitting a facility to process enciphered data
arriving from outside without mounting any special programming effort.   At  the
same  time,  those  ciphers most used in a given facility could be hand coded or
implemented in hardware for efficiency.

	This effort should be accompanied by an attempt  to  integrate  suitable
indicators  into  standard  data  formats.    Such data structures as files in a
storage system, records on a tape, and packets traveling  on  a  network,  would
then  have  built  in  information telling whether they were encrypted and under
what cryptosystem. This would obviate future difficulties in  replacing  systems
which proved insecure or merely uneconomical.


				References

1.	G. Gordon Benedict, "An Enciphering Module for  Multics"  MAC  Technical
	Memorandum 50, MIT July 1974

2.	Horst Feistel, "Cryptographic coding for data-bank privacy"  IBM  Thomas
	J.  Watson Research Center Yorktown Heights, New York, RC-2827, 18 March
	1970, pp ii+56

3.	Horst  Feistel,  William  Notz,  and  J.   Lynn  Smith,   "Cryptographic
	Techniques  for  Machine  to  Machine Data Communications" IBM Thomas J.
	Watson Research Center, Yorktown Heights, New York, 27 December 1971, pp
	i+34

4.	Horst  Feistel,  "Cryptography and Computer Privacy" Scientific American
	Vol. 228, No. 5 May 1973 pp 15-23

5.	Edna Grossman and Don Coppersmith, "Generators for  Certain  Alternating
	Groups  with  Applications  to  Cryptography"  26 Feb 1974, RC 4741, IBM
	Watson Research Center, Yorktown Heights, New York, pp ii+10

6.	Edna Grossman, "Group Theoretic Remarks on Cryptographic  Systems  Based
	on  Two  Types  of  Addition", 26 Feb 1974, RC 4742, IBM Watson Research
	Center, Yorktown Heights, New York, pp ii+15

7.	Richard R. Keys and Eric H. Clamons,  "File  Encryption  as  a  Security
	Tool" The Honeywell Computer Journal, Vol 8 No 2, 1974, pp 90-93

8.	National Bureau of Standards "Encryption  Algorithm  for  Computer  Data
	Protection" Federal Register, 17 March 1975

9.	J.    Lynn  Smith,  "The  Design of Lucifer,  A Cryptographic Device for
	Data Communications" IBM White Plains, N. J., RC 3326

10.	J.  Lynn Smith, William A. Notz, and P.  R.   Osseck,  "An  Experimental
	Application  of  Cryptography  to a Remotely Accessed Data System" Proc.
	ACM Conference 1972, pp 282-297